package Greedy;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@SuppressWarnings("all")
public class 海盗装载问题 {
    /**
     * 典型的贪心算法的求解的问题：每次从商品中选择一件重量最小的进行装载，从局部到整体
     * @param args
     */
    public static void main(String[] args) {
        int[] weights = {3,5,4,10,7,14,2,11}; // 每件商品的重量
        int capacity = 30; // 最大承重
        int count = 0; // 记录最终可以装载的最大数量
        int weight = 0; // 记录当前存放货物的重量
        List<Integer> goods = new ArrayList<>(); // 存放最终的装载的货物
        Arrays.sort(weights); // 对weights数组进行从下到大的排序
        while (weights[count] < capacity - weight) {
            weight += weights[count];
            goods.add(weights[count]);
            count++;
        }
        System.out.println("最大装载货物的数量："+count);
        System.out.println("装载的货物分别是：");
        for (Integer good : goods) {
            System.out.print(good+" ");
        }
    }
}
